package com.sx.sx1.lintcode.day717;

import java.util.ArrayList;
import java.util.List;

public class LC1297 {

    static class Solution {
        /**
         * @param nums: a list of integers
         * @return: return a list of integers
         */
        public List<Integer> countSmaller(int[] nums) {
            // 区间是最大值-最小值+1  最小值如果大于0，就是0，一定要记住解法
            int n= nums.length;
            List<Integer> ans = new ArrayList<>();
            if(n ==0) return ans;
            int max=Integer.MIN_VALUE,min =Integer.MAX_VALUE;
            for (int cur : nums) {
                max = Math.max(max,cur);
                min = Math.min(min,cur);
            }

            min = Math.min(min,0);
            SegmentNode root= buildTree(0,max-min); //线段树头节点，可能为负数，因此大数减去小数
            for (int i = n-1; i >=0 ; i--) {
                int idx = nums[i]+Math.abs(min);
                if(nums[i] == min){
                    ans.add(0,0);
                }else{
                    int query = query(root,0,idx-1);
                    ans.add(0,query);
                }

                update(root,idx,1);
            }

            return ans;
        }

        public SegmentNode buildTree(int start,int end){
            if(start == end) return new SegmentNode(start,end);
            SegmentNode root = new SegmentNode(start,end);
            int m = start+(end-start)/2;
            root.left = buildTree(start,m);
            root.right = buildTree(m+1,end);
            return root;
        }

        public int query(SegmentNode root,int start,int end){
            if(root.start == start && root.end == end)
                return root.sum;

            int m = root.start+(root.end-root.start)/2;
            int left =0,right =0;
            if(m>=start) {
                left = query(root.left,start,Math.min(m,end));

            }

            if(m<end){
                right = query(root.right,m>=start?m+1:start,end);
            }

            return left+right;
        }

        public void update(SegmentNode root,int idx,int addv){
            if(root.start== root.end && root.start == idx){
                root.sum += addv;
                return;
            }

            int m = root.start+(root.end-root.start)/2;
            if(idx<= m){
                update(root.left,idx,addv);
            }else{
                update(root.right,idx,addv);
            }

            root.sum = root.left.sum+root.right.sum;
        }
        static class SegmentNode{
            public int start,end,sum;
            public SegmentNode left,right;
            public SegmentNode(int s,int e){
                start=s;
                end =e;
            }
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.countSmaller(new int[]{5,2,6,1}));
        System.out.println(obj.countSmaller(new int[]{1,2,3,4}));
    }



    static class Solution123 {
        /**
         * @param nums: a list of integers
         * @return: return a list of integers
         */
        public List<Integer> countSmaller(int[] nums) {
            int n= nums.length;
            List<Integer> ans = new ArrayList<>();
            if(nums ==null|| n==0) return ans;
            int max =Integer.MIN_VALUE,min=Integer.MAX_VALUE;
            for (int num : nums) {
                max =Math.max(max,num);
                min =Math.min(min,num);
            }
            min =Math.min(min,0);

            Node root = buildTree(0,max-min); //线段树头节点,可能有负数，因此大数减去小数
            for (int i = n-1; i >=0 ; i--) {
                int index= nums[i]+Math.abs(min);
                if(nums[i] ==min){
                    ans.add(0,0);
                }else{
                    int query=query(root,0,index-1);
                    ans.add(0,query);
                }

                update(root,index,1);
            }
            return ans;
        }


        public static Node buildTree(int start,int end){
            Node root = new Node(start,end);
            if(start ==end) return root;
            int mid = start+(end-start)/2;
            root.left = buildTree(start,mid);
            root.right = buildTree(mid+1,end);
            return root;
        }

        public static int query(Node root,int start,int end){
            if(root.start ==start && root.end ==end)
                return root.sum;
            int mid = root.start+(root.end-root.start)/2;
            int left=0,right=0;
            if(mid>=start){
                if(mid<end) left= query(root.left,start,mid);
                else left= query(root.left,start,end);
            }

            if(mid<end){
                if(mid>=start) right = query(root.right,mid+1,end);
                else right = query(root.right,start,end);
            }
            return left+right;
        }

        public static void update(Node root,int index,int value){
            if(root.start ==root.end && root.start ==index){
                root.sum +=value;
                return;
            }

            int mid=root.start+(root.end-root.start)/2;

            if(index>= root.start && index<=mid){
                update(root.left,index,value);
            }

            if(index>=mid+1&& index<=root.end){
                update(root.right,index,value);
            }

            root.sum =root.left.sum+root.right.sum;
        }
        static class Node{
            int start,end,sum;
            Node left,right;
            public Node(int s,int e){
                start=s;
                end =e;
            }
        }

    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有887条未读消息，请及时查看
新增3条赞
1297 · 比自己小的元素个数
算法
困难
通过率
46%

题目
题解21
笔记
讨论34
排名
记录
描述
给定一个整数数组nums，返回一个新的counts数组。counts[i]表示：nums[i]右侧比它小的数的个数。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例1

输入: [5, 2, 6, 1]
输出: [2, 1, 1, 0]
说明:
5的右侧有2个元素比它小 (2 and 1).
2的右侧有1个元素比它小 (1).
6的右侧有1个元素比它小 (1).
1的右侧有0个元素比它小.
样例2

输入: [1, 2, 3, 4]
输出: [0, 0, 0, 0]
标签
企业
Google
相关题目

1252
根据身高重排队列
中等
推荐课程

系统设计 System Design 2024版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
已开启智能提示
发起考试
45 分 00 秒
123456789
public class Solution {
    /**
     * @param nums: a list of integers
     * @return: return a list of integers

public List<Integer> countSmaller(int[] nums) {
    // write your code here
}
}
控制台
        历史提交

 */
